1. Field of the Invention
The present invention relates to a cache hit ratio estimating system, a cache hit ratio estimating method, a program and a recording medium. More particularly, this invention relates to a cache hit ratio estimating system, a cache hit ratio estimating method, a program and a recording medium in which the cache hit ratio is estimated for a plurality of access object data that are different in the access cost at the time of cache miss.
2. Background Art
Server devices running Web applications today cache data accessed by components such as a HTTP server, Web container, EJB container, and database server, on a component-by-component basis, in order to reduce both workload and response time. The performance of an application that uses such caching is determined by the cache hit ratio for each of access target data, response time required when a cache hit occurs, and access processing time required when a cache miss occurs. However, because the impact of cache setting parameters on the cache hit ratio is not quantitatively obvious, the parameter has been set heuristically.
Approaches to estimating the hit ratio of caches based on LRU (Least Recently Used) have been proposed in non-patent documents 1 to 4.
The approach proposed in P. J. Burville and J. F. C. Kingman, “On a model for storage and search.”, Journal of Applied Probability, 10: pp. 697-701, 1973 calculates the probability that an item to be cached is in the n-th position on an LRU list when an access request is received by using Equation (1).
                    [                  Equation  1                ]                                                                      P          ⁡                      [                                          C                N                            =              n                        ]                          =                              ∑                          r              =              1                        N                    ⁢                                    ∑                              a                =                0                                            n                -                1                                      ⁢                                                            (                                      -                    1                                    )                                                  n                  -                  1                  -                  a                                            ⁢                              (                                                                                                    N                        -                        1                        -                        a                                                                                                                                                n                        -                        1                        -                        a                                                                                            )                            ⁢                                                ∑                                                                                    A                        :                                                                            A                                                                                              =                      a                                        ,                                          r                      ∉                      A                                                                      ⁢                                                      q                    r                    2                                                        (                                          1                      -                                              Q                        A                                                              )                                                                                                          (        1        )                                          where          ⁢                                          ⁢                      Q            A                          ≡                              ∑                          r              ∈              A                                ⁢                      q            r                                                          where CN represents the reference cost of all items (the position on the list of the items of access target data when access request is received) and qr represents the probability that item r (r=1, 2, . . . , N) will be accessed.
Using Equation (1), the hit ratio of an LRU cache that caches k items can be calculated with P[CN≦k].
The approaches in P. Flajolet, D. Gardy, and L. Thimonier, “Birthday paradox, coupon collector, caching algorithms and self-organizing search.”, Discrete Applied mathematics, 39: pp. 207-229, 1992, and J. A. Fill and L. Holst, “On the distribution search cost for the move-to-front rule.”, Random Structures and algorithms, 8(3): pp. 179-186, 1996 calculate the probability generating function of the reference cost CrN of each item by using Equation (2).
                    [Equation  2]                                                                      E          ⁡                      [                          z                              C                N                                      ]                          =                              ∑                          i              =              1                        N                    ⁢                                    q              1                        ⁢                          E              ⁡                              [                                  z                                      C                    i                    N                                                  ]                                                                        (        2        )                                          E          ⁡                      [                          z                              C                r                N                                      ]                          =                              ∫            0            ∞                    ⁢                                    q              r                        ⁢                                          ⅇ                                  -                                      q                    r                    t                                                              [                                                ∏                                      j                    ∈                                                                                            [                          N                          ]                                                ⁢                                                  :                                                ⁢                        j                                            ≠                      r                                                                      ⁢                                                      (                                                                  ⅇ                                                  -                                                      q                            j                            t                                                                                              +                                              (                                                  1                          -                                                      ⅇ                                                          -                                                              q                                j                                t                                                                                                                                    )                                                              ]                                    ⁢                                      ⅆ                    t                                                                                                                      
P. R. Jelenkovic, “Asymptotic approximation of the move-to-front search cost distribution and least-recently-used caching fault probabilities.”, Annals of Applied Probability, 9(2): pp. 430-464, 1999 shows the following Equations (3-1) and (3-2) as asymptotic approximate expressions for the case where the number N of items and the cache size k approach infinity. Equation (3-1) is an approximate expression for the case where the reference probability distribution of an item decreases in the multinomial (Heavy Tail) and Equation (3-2) is an approximate expression for the case where the reference probability distribution decreases exponentially (Light Tail). Furthermore, the document has demonstrated by experiment that the precision of the approximate expressions is high even if N and k are relatively small values.
                    [Equation  3]                                                                                  lim                          k              →              ∞                                ⁢                                    P              ⁡                              [                                                      C                    ∞                                    >                  k                                ]                                                    P              ⁡                              [                                                      R                    ∞                                    >                  k                                ]                                                    =                              (                          1              -                              1                α                                      )                    ⁡                      [                          Γ              ⁡                              (                                  1                  -                                      1                    α                                                  )                                      ]                                              (                  3          ⁢                      -                    ⁢          1                )                                          if          ⁢                                          ⁢                      P            ⁡                          [                                                R                  ∞                                -                n                            ]                                      ≈                  c          /                      n            α                                                                                                    lim                          k              →              ∞                                ⁢                                    P              ⁡                              [                                                      C                    ∞                                    >                  k                                ]                                                    P              ⁡                              [                                                      R                    ∞                                    >                  k                                ]                                                    =                                            ⅇ              r                        ⁢                                                  ⁢            if            ⁢                                                  ⁢                          P              ⁡                              [                                                      R                    ∞                                    =                  n                                ]                                              ≈                      c            ⁢                                                  ⁢                          ⅇ                                                -                  λ                                ⁢                                                                  ⁢                n                ⁢                                                                  ⁢                β                                                                        (                  3          ⁢                      -                    ⁢          2                )            
It is difficult to heuristically determine an optimum value of a cache setting parameter suitable for the execution environment of an application. For example, one method for calculating optimum values of setting parameters may be to change setting parameters while repeating performance measurements to obtain optimum setting parameters when building an information system. However, this method is burdensome and cannot keep up with a dynamically changing application execution environment.
Therefore, a need exists for a cache system in which more preferable setting parameters are calculated on the basis of various kinds of statistics measured during the runtime of an application and are set for a cache in order to improve the performance of the cache. In particular, a need exists for an estimation function for estimating the performance of access processing is generated on the basis of various statistics and setting parameters that increase estimations for access processing performance are calculated and set for the cache.